package com.sufen.seckill.study.LeetCode;

/**
 * @Author sufen
 * @Date 2021/11/5 16:07
 * @Version 1.0
 * 功能描述：
 */
public class Offer_12_矩阵中的路径 {
    public static void main(String[] args) {
        char[][] testChar={{'A','B','C','D','E','F','G'},{'A','B','C','D','E','F','G'},{'A','B','C','D','E','F','G'}};
        /**
         * ABCDEFG
         * ABCDEFG
         * ABCDEFG
         */
        String word="ABCDDDEFGGG";
        System.out.println(exist(testChar,word));
    }
    // char[][] board;
    // String word;
    public static int length_hang;
    public static int length_lie;
    public static int length_word;

    public static boolean exist(char[][] board, String word) {
        // board=this.board;
        // word=this.word;

        length_hang=board.length;
        length_lie=board[0].length;
        length_word=word.length();

        boolean[][] b=new boolean[length_hang][length_lie];

        int index=0;

        boolean res=false;

        for(int i=0;i<length_hang;i++){
            for(int j=0;j<length_lie;j++){
                if(recur(i,j,b,0,board,word)==true){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean recur(int i,int j,boolean[][] b,int index,char[][] board, String word){
        if(i<0||i>=length_hang||j<0||j>=length_lie||b[i][j]==true){
            return false;
        }
        //找到了
        if(word.charAt(index)==board[i][j]&&index==length_word-1){
            return true;
        }

        //不对，中止
        if(!(word.charAt(index)==board[i][j])){
            return false;
        }

        //暂时对，继续搜
        b[i][j]=true;
        boolean res=recur(i+1,j,b,index+1,board,word)||recur(i-1,j,b,index+1,board,word)||recur(i,j+1,b,index+1,board,word)||recur(i,j-1,b,index+1,board,word);
        b[i][j]=false;
        return res;
    }
}
